分治法(Divide and Conquer)把一個複雜的問題分成一個或多個相似的子問題，直到子問題能夠簡單求解，則此時原本的問題即為子問題的合併。

Weak Induction
假設在n=k時P(k)是正確的，基於如此P(k+1)也會是對的，每次只前進一步。
Strong Induction
假設在n=k時P(k)以下(<=k)都是正確的，亦即P(0)∧ P(1)..∧ P(k)，基於如此P(k+1)也會是對的。

Searching是在學習演算法中重要的一個環節，主要是想要在已經排序或是未排序的序列中找到目標的元素，以下羅列常見的searching method:

以下是三種搜尋演算法的介紹：

1. Sequential Search（循序搜尋）

循序搜尋是一種簡單的搜尋演算法，適用於未排序的資料。它逐一檢查資料集中的每個元素，直到找到目標元素或遍歷完整個資料集，當資料集未排序或資料量較小時，Sequential Search 是一種直接而有效的搜尋方法。
時間複雜度：(O(n))，其中 (n) 是資料集中元素的數量。當資料集較大時，效率不高。

def sequential_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 找到目標，返回索引
    return -1  # 如果未找到目標，返回 -1

arr = [3, 5, 2, 9, 1]
target = 9
result = sequential_search(arr, target)
print(f'Sequential Search Result: {result}')

2. Binary Search（二元搜尋）

二元搜尋是一種高效的搜尋演算法，適用於已排序的資料。它通過反覆將搜尋範圍對半分割，逐步縮小範圍以找到目標元素，適用於已排序的資料集，尤其當資料集較大時，效率明顯優於 Sequential Search。

首先從已排序的資料集的中間元素開始比較，如果目標元素小於中間元素，則搜尋範圍縮小到左半部分。如果目標元素大於中間元素，則搜尋範圍縮小到右半部分，直到找到目標元素或範圍縮小為零。
時間複雜度：(O(\log n))，其中 (n) 是資料集的大小。

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid  # 找到目標，返回索引
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    
    return -1  # 如果未找到目標，返回 -1

arr = [1, 2, 3, 5, 9]
target = 5
result = binary_search(arr, target)
print(f'Binary Search Result: {result}')

3. Exponential Search（指數搜尋）

指數搜尋是一種適用於已排序資料集的搜尋演算法，特別適合於搜尋範圍未知的情況。它首先以指數增長的方式找到一個範圍，然後在這個範圍內使用 Binary Search 進行搜尋， 適用於已排序的無限或非常大的資料集，尤其在搜尋範圍未知或無法直接計算範圍的情況下。

從資料集的第1個元素開始，逐步以2的指數增長（1, 2, 4, 8, ...）來檢查元素，直到找到比目標元素大的第一個元素或超出資料集範圍，使用 Binary Search 在確定的範圍內搜尋目標元素。

時間複雜度：在最壞情況下為 (O(\log n))，但在目標元素接近起始點時，效率可能更高。

def binary_search(arr, target, low, high):
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

def exponential_search(arr, target):
    if arr[0] == target:
        return 0
    
    i = 1
    while i < len(arr) and arr[i] <= target:
        i = i * 2
    
    return binary_search(arr, target, i // 2, min(i, len(arr) - 1))

arr = [1, 2, 3, 5, 9, 12, 15, 18, 21, 25]
target = 18
result = exponential_search(arr, target)
print(f'Exponential Search Result: {result}')

大家再撐下去呀，再過三個章節，我們就要開始機器學習的航海大道了！